/*
题目: 丑数Ⅱ
给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 或 5 的正整数。

https://leetcode.cn/problems/ugly-number-ii/
 */
public class NthUglyNumber {
    public int nthUglyNumber(int n) {
        // 表示第 n 个丑数是谁
        int[] dp = new int[n + 1];
        dp[1] = 1;

        // 分别表示三个能被 2, 3, 5 整除的递增数组, 然后开始合并这 3 个数组
        // 然后计算合并后的数组下一位应该是哪个, 谁奉献了这一位, 谁就往后移动

        int p2 = 1, p3 = 1, p5 = 1; // 并且表示的是 下标
        for (int i = 2; i <= n; i ++) {
            // 计算下一位丑数
            int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
            // 得出下一位丑数
            dp[i] = Math.min(num2, Math.min(num3, num5));
            // 谁奉献的谁就往前走
            if (dp[i] == num2) {
                p2 ++;
            }
            if (dp[i] == num3) {
                p3 ++;
            }
            if (dp[i] == num5) {
                p5 ++;
            }
        }

        return dp[n];
    }
}
